import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution2227 {

    Map<Character,Integer> keyMap=new HashMap<>();
    Map<String, List<Integer>> valueMap=new HashMap<>();
    Trie trie=new Trie();
    char[] keys;
    String[] values;
    String[] dictionary;

    static class Trie{
        Trie[] children=new Trie[26];
        boolean end;

        public void insert(String s){
            Trie node=this;
            for (char c : s.toCharArray()) {
                if (node.children[c-'a']==null){
                    node.children[c-'a']=new Trie();
                }
                node=node.children[c-'a'];
            }
            node.end=true;
        }
    }

    public Solution2227(char[] keys, String[] values, String[] dictionary) {
        this.keys=keys;
        for (int i=0;i<keys.length;i++){
            keyMap.put(keys[i],i);
        }
        this.values=values;
        for (int i=0;i<values.length;i++){
            valueMap.putIfAbsent(values[i],new ArrayList<>());
            valueMap.get(values[i]).add(i);
        }
        this.dictionary=dictionary;
        for (String s : dictionary) {
            trie.insert(s);
        }
    }

    public String encrypt(String word1) {
        StringBuilder stringBuilder=new StringBuilder();
        for (char c : word1.toCharArray()) {
            stringBuilder.append(values[keyMap.get(c)]);
        }
        return stringBuilder.toString();
    }

    int ans=0;

    public int decrypt(String word2) {
        ans=0;
        dfs(word2,0,new StringBuilder(),trie);
        return ans;
    }

    private void dfs(String word, int k,StringBuilder stringBuilder,Trie trie) {
        if (k==word.length()){
            if (trie.end){
                ans++;
            }
            return;
        }
        String val=word.substring(k,k+2);
        List<Integer> list=valueMap.getOrDefault(val,null);
        if (list==null){
            return;
        }
        for (Integer integer : list) {
            if (trie.children[keys[integer]-'a']==null){
                continue;
            }
            stringBuilder.append(keys[integer]);
            dfs(word,k+2,stringBuilder,trie.children[keys[integer]-'a']);
            stringBuilder.deleteCharAt(stringBuilder.length()-1);
        }
    }

    public static void main(String[] args) {
        Solution2227 solution2227 = new Solution2227(new char[]{'a', 'b', 'c', 'd'}, new String[]{"ei", "zf", "ei", "am"}, new String[]{"abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"});
        System.out.println(solution2227.encrypt("abcd"));
        System.out.println(solution2227.decrypt("eizfeiam"));
    }
}
